
public class AlgoritmFloyd_Warshall
{
	private GrafOrientat graf;
	private int[][] d , p;
	private int n ,inf = 999999999;
	
	public AlgoritmFloyd_Warshall(GrafOrientat graf) 
	{
		this.graf = graf;
		n = graf.getNrVarfuri();
		
		d = new int [n][n];
		p = new int [n][n];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				d[i][j] = inf;
		
		int m = graf.getNIncidenta();
		Muchie e[] = new Muchie[m];
		e = graf.getListaInc();
		
		for(int i=0;i<m;i++)
		{
			d[e[i].from][e[i].to] = e[i].val;
			
			if(e[i].from != e[i].to && d[e[i].from][e[i].to] < inf)
				p[e[i].from][e[i].to] = e[i].from;
			else
				p[e[i].from][e[i].to] = 0;
		}
			
	}
	
	private void alg()
	{
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
					if(d[i][k] + d[k][j] < d[i][j])
					{
						d[i][j] = d[i][k] + d[k][j];
						p[i][j] = p[k][j];
					}
	}
	
	public String getRezultat(int i , int j)
	{
		alg();
		String s = " ";
		int [] a = new int[n+1];
		
		int k = n;
		a[k] = j;
		
		while(a[k] != i)
		{
			a[k-1] = p[i][a[k]];
			k--;
		}
		
		for(int l=k;l<=n;l++)
			s = s+a[l]+" ";
		
		return s+"\n Costul total este "+d[i][j];
	}
	
}
